package com.cuz.daileetcode;

public class Day58 {


    public static class MaximumCumulativeSumOfSubMatrix {
        public static void main(String[] args) {
            int[][] matrix = {
                    {1, 2, 3, -4},
                    {-1, 2, 3, 4},
                    {-1, 2, 3, -100}
            };
            System.out.println(solution1(matrix));
        }

        static int solution1(int[][] matrix) {
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
                return 0;
            }
            int res = Integer.MIN_VALUE;
            // 0-0 行最大累加和  0-1行最大累加和 0-2，0-3.。。。 1到1行最大累加和
            int maxRow = matrix.length;
            //从开始行 到最后一行  计算其中的最大矩阵之和
            for (int startRow = 0; startRow < maxRow; startRow++) {
                //开始行的数组
                int[] temp = matrix[startRow];
                for (int endRow = startRow; endRow < maxRow; endRow++) {
                    //如果不等 那么把结束行的累加到开始行数组之上
                    //因为矩阵必须是矩形，所有列是对齐的，不可以选择第一行的某列，企图和第二行构成矩阵
                    //但是不选择第二行的此列
                    //startRow=0 endRow等于1 会把01加起来就计算了 0到1最大子矩阵之和
                    //然后endRow=2 又会把 第二行加起来就计算了 012的累加和
                    if (startRow != endRow) {
                        temp = addTowArray(temp, matrix[endRow]);
                    }
                    //计算单个数组 最大连续数组之和
                    res = Math.max(subArraySum(temp), res);
                }
            }
            return res;
        }

        private static int[] addTowArray(int[] arr1, int[] arr2) {
            int len = arr1.length;
            int[] res = new int[len];
            for (int index = 0; index < arr1.length; index++) {
                res[index] = arr1[index] + arr2[index];
            }
            return res;
        }

        /***
         * 子数组最大累加和
         * @param arr 数组
         * @return 最大累加和
         */
        private static int subArraySum(int[] arr) {
            int cur = 0;
            int max = Integer.MIN_VALUE;
            for (int temp : arr) {
                cur += temp;
                max = Math.max(max, cur);
                if (cur < 0) {
                    cur = 0;
                }
            }
            return max;
        }
    }

    public static class MinLamps {

        public static void main(String[] args) {
            String s = ".xxx..xx...xx.......";
            System.out.println(solution1(s));
            System.out.println(solution2(s));
        }

        public static int solution1(String s) {
            if (s == null || s.length() == 0) {
                return 0;
            }
            char[] charArray = s.toCharArray();
            int res = 0;
            //上一个路灯的位置 -1代表没有放路灯
            int pre = -1;
            for (int index = 0; index < charArray.length; index++) {
                //如果这个地方需要被照亮
                if (charArray[index] == '.') {
                    //从没有放过路灯，或者路灯距离自己大于两个位置 那么放下路灯
                    if (pre < 0 || index - pre > 2) {
                        pre = index;
                        //路灯数++
                        res++;
                    }
                }
            }
            return res;
        }

        public static int solution2(String s) {
            if (s == null || s.length() == 0) {
                return 0;
            }
            char[] charArray = s.toCharArray();
            int res = 0;
            //累计有多少个连续的字符没有被点亮
            int cumulativeContinuous = 0;
            for (char c : charArray) {
                //不是.说明不需要照亮
                if (c != '.') {
                    //但是之前已经存在了路灯没有被点亮
                    if (cumulativeContinuous != 0) {
                        //点亮
                        res++;
                    }
                    //设置连续没被点亮为0 因为之前的已经被点亮了
                    cumulativeContinuous = 0;
                } else {
                    //是.   这个位置需要被点亮
                    cumulativeContinuous++;
                    //如果累计达到3个
                    if (cumulativeContinuous == 3) {
                        //节约路灯 一次性点亮
                        res++;
                        //设置连续为0
                        cumulativeContinuous = 0;
                    }
                }
            }
            //如果结束了还有一些地方没有被点亮
            if (cumulativeContinuous != 0) {
                //使用一个路灯点亮
                res++;
            }
            return res;
        }
    }
}
